package features.advance.leetcode.linkedlist.medium;

import features.advance.leetcode.geometry.doublepointer.easy.ListNode;
import features.advance.leetcode.util.TreeUtil;

/**
 * 92. 反转链表 II
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 *
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 *
 * 提示：
 *
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *
 *
 * 进阶： 你可以使用一趟扫描完成反转吗？
 *
 *
 * @author LIN
 * @date 2021-04-22
 */
public class Solution92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null){
            return head;
        }
        if(left == right){
            return head;
        }
        ListNode prev = null;

        ListNode curr = head;
        ListNode leftNode = null,leftP = null,rightNode = null,rightA=null;
        int i = 0;
        while(curr != null){
            i++;
            if(i == left){
                leftNode = curr;
                leftP = prev;
                if(prev != null){
                    prev.next = null;
                }

            }
            if(i == right){
                rightNode = curr;
                rightA = curr.next;
                rightNode.next = null;
            }
            ListNode next = curr.next;

            prev = curr;
            curr = next;

        }
        leftNode = reverseList(leftNode);
        if(leftP != null){
            leftP.next = leftNode;
        }else{
            head = leftNode;
        }
        ListNode a = head;
        while(a != null){
            if(a.next == null){
                a.next = rightA;
                break;
            }
            a = a.next;

        }
        return head;
    }
    public ListNode reverseList(ListNode head) {

        ListNode prev = null;

        ListNode curr = head;

        while(curr != null){
            ListNode next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {

        String str = "[1,2,3,4,5]";
        int left = 2,right=4;
        ListNode head = TreeUtil.parseLinkedList(str);
        ListNode listNode = new Solution92() {
            @Override
            public ListNode reverseBetween(ListNode head, int left, int right) {
                // 设置 dummyNode 是这一类问题的一般做法
                ListNode dummyNode = new ListNode(-1);
                dummyNode.next = head;
                ListNode pre = dummyNode;
                for (int i = 0; i < left - 1; i++) {
                    pre = pre.next;
                }
                ListNode cur = pre.next;
                ListNode next;
                for (int i = 0; i < right - left; i++) {
                    next = cur.next;
                    cur.next = next.next;
                    next.next = pre.next;
                    pre.next = next;
                }
                return dummyNode.next;
            }
        }.reverseBetween(head, left, right);

        System.out.println(listNode);
    }
}
